Recurrence Relations

Recurrence Relations ( a brief intro)

Let {an}n=0+∞\left\{a_{n}\right\}_{n=0}^{+\infty} be a sequence of numbers, real or complex

A recurrence relation is a rule, or function, that defines the general term ana_{n} in terms of one ore more of the preceding terms, a0,a1,…,an−1a_{0}, a_{1}, \ldots, a_{n-1}

That is, an=f(a0,a1,⋯ ,an−1),∀n=1,2,⋯a_{n}=f\left(a_{0}, a_{1}, \cdots, a_{n-1}\right), \forall n=1,2, \cdots

A solution of a recurrence relation is a sequence {an}n=0+∞\left\{a_{n}\right\}_{n=0}^{+\infty} whose terms satisfy the recurrence relation

Recurrence relations can have more than one solution. To ensure that a recurrence relation has exactly one solution, we can specify initial conditions for our solution

These are just specific values for some terms a0,a1,…,an0a_{0}, a_{1}, \ldots, a_{n_{0}} of a solution.

We will look at a number of examples to clarify these concepts

Example 1 The number of bacteria in a colony doubles every hour. If we initially have 5 bacteria to begin with, how many are there after 5 hours? after nn hrs?

We start with 5 , so after

Time (hours) Number of Bacteria
0 5
1 10
2 20
3 40
4 80
5 160

Now if we let an=a_{n}= number of bacteria after nn hours, we have the recurrence relation

(i) an=2an−1,n=1,2,3⋯a_{n}=2 a_{n-1}\qquad, \qquad n=1,2,3 \cdots

with the initial condition

(ii) a0=5a_{0}=5

Equations (i) a (ii) together form an "initial value recurrence relation" with a unique solution {an}x=0+∞\left\{a_{n}\right\}_{x=0}^{+\infty} with a0=5a_{0}=5.

Thus after nn hours we have ana_{n} bacteria where

an=2an−1a0=5 \begin{array}{l} a_{n}=2 a_{n-1} \\ a_{0}=5 \end{array}

Example 2 Classical Example due to Leonardo di Pisa aka Fibonacci 13th century AD book "Liber Abaci" Italian for counting numbers where does the word abbacus comes from

A young pair of rabbits, I male, I female, are put on an island. A pair of rabbit can't breed until they are 2 months old. after they are 2 months old, each pain produces another pair each month. assuming no deaths "find the number of rabbits after the nn month" (ie find a recurrence relation for these numbers)

To analyze the situation consider the following chart:

 Month  Reproducing  Young  Pairs  Total  Pairs 101120113112412352356358\begin{array}{cccc}\text { Month } & \text { Reproducing } & \begin{array}{c}\text { Young } \\ \text { Pairs }\end{array} & \begin{array}{c}\text { Total } \\ \text { Pairs }\end{array} \\ 1 & 0 & 1 & 1 \\ 2 & 0 & 1 & 1 \\ 3 & 1 & 1 & 2 \\ 4 & 1 & 2 & 3 \\ 5 & 2 & 3 & 5 \\ 6 & 3 & 5 & 8\end{array}

Let fn=f_{n}= number pairs of rabbits after nn months. We have f1=f2=1f_{1}=f_{2}=1 since there is no breeding going on. That is each new pair comes from a pair at least 2 months old

To determine the recurrence relation we employ backwards reasoning.

Let n⩾3n \geqslant 3.

If the number of pairs in the nnth month is fnf_{n}, it is equal to the number of pairs in month n−1,fn−1n-1, f_{n-1}, plus the number of new born pairs. The number of new born pairs is equal to the number of pairs at least 2 months old, ie fn−2f_{n-2},

 Thus fn=fn−1+fn−2,n=3,4,⋯ and f1=1f2=1\begin{aligned} \text { Thus } \quad f_{n} & =f_{n-1}+f_{n-2}, \quad n=3,4, \cdots \\ \text { and } \quad f_{1} & =1 \\ f_{2} & =1 \end{aligned}

The recurrence relation with initial conditions (2) has a unique solution called\
The Fibonacci numbers (Fibonacci' Sequence)

ff={1,1,2,3,5,8,13,21,34,55,89,144,⋯ }={fn}n=1∞ \begin{aligned} f^{f} & =\{1,1 , 2 , 3,5,8,13,21,34,55,89,144, \cdots\} \\ & =\left\{f_{n}\right\}_{n=1}^\infty \end{aligned}

Example 3 (Related)

A flight of stairs has nn steps that one can climb one step at a time or two steps at a time. How many ways can one climb the stairs?

Let tn=t_{n}= number of ways to get to the nth n^{\text {th }} step Our last step is either 1 step or 2 steps

Thus tn=tn−1+tn−2t_{n}=t_{n-1}+t_{n-2}

Now

t1=1t2=2 \begin{aligned} & t_{1}=1 \\ & t_{2}=2 \end{aligned}


And tnt_{n} satisfies

tn=tn−1+tn−2t1=1t2=2} \left.\begin{array}{l} t_{n}=t_{n-1}+t_{n-2} \\ t_{1}=1 \\ t_{2}=2 \end{array}\right\}

and

J={1,2,3,5,8,13,⋯ } J=\{1,2,3,5,8,13, \cdots\}

Clearly tx=fx+1t_{x}=f_{x+1} from example 2

Exercise Let an=a_{n}= number of bit strings of length nn that do not have 2 consecutive zeros

Show a1=2,a2=3a_{1}=2, a_{2}=3 and that an=fn+2=n+2nda_{n}=f_{n+2}=n+2^{n d} Fibonacci number

Example 3 Suppose we have a computer system that considers a string of decimal digits a valid codeword if it has an even number of 0 digits. Fore example

120430900 valid 120430901 invalid  \begin{aligned} & 120430900 \text { valid } \\ & 120430901 \text { invalid } \end{aligned}

Let an=a_{n}= number of valid nn digit codewords
Find a recurrence relation for ana_{n}.

Fist note a1=9a_{1}=9, since 0 is the only invalid I digit string.

How do we get a valid nn-digit string from a string n−1n-1 digit long.

2 ways:
i) append 1−91-9 onto a valid x−1x-1 digit string in 9an−19 a_{n-1} ways
ii) append 0 to an invalid x−1x-1 digit sting

Now there are 10n−1n−110^{n-1}\qquad n-1 digit strings of which an−1a_{n-1} are valid,
so there are 10n−1−an−110^{n-1}-a_{n-1} invalid n−1n-1 digit strings

Thus

an=9⋅an−1+(10n−1−an−1), That is an=8⋅an−1+10n−1,a1=9 \begin{aligned} a_{n} & =9\cdot a_{n-1}+\left(10^{n-1}-a_{n-1}\right), \\ \text { That is }\qquad a_{n} & =8\cdot a_{n-1}+10^{n-1}, \\ a_{1} & =9 \end{aligned}

The Recurrence Relation (1) - (4) give us information on how to calculate the general term ana_{n}, using terms that came before, starting from our initial conditions

It can be impractical to calculate ana_{n} from the recurrence relation, and we cant really investigate the long term behavior (as n→+∞n \rightarrow+\infty ).

If we can find a formula an=f(n)a_{n}=f(n) for the general term we call it a closed form of the solution

Let us reconsider (1)

an=2an−1a0=5 \begin{aligned} & a_{n}=2 a_{n-1} \\ & a_{0}=5 \end{aligned}

We have

a1=2⋅5a2=2⋅a1=2⋅2⋅5=22⋅5a3=2a2=2⋅22⋅5=23⋅5⋮an=2⋅an−1=2⋅2n−1⋅5=2n⋅5⋮by induction \begin{aligned} & a_{1}=2 \cdot 5 \\ & a_{2}=2 \cdot a_{1}=2 \cdot 2 \cdot 5=2^{2} \cdot 5 \\ & a_{3}=2 a_{2}=2 \cdot 2^{2} \cdot 5=2^{3} \cdot 5 \\ & \vdots \\ & a_{n}=2 \cdot a_{n-1}=2 \cdot 2^{n-1} \cdot 5=2^{n} \cdot 5\\ & \vdots \quad \text{by induction}\\ \end{aligned}

Thus

an=f(n)=2n⋅5 is a closed form solution of (1) a_{n}=f(n)=2^{n} \cdot 5 \text { is a closed form solution of (1)}

This method of finding a closed form solution (assuming it exists) of a recurrence relation is called iteration. It in not in general of much use.

It would be nice to be able to "write down" the closed solution of a recurrence relation. This is not possible for all recurrence relations but there is a special type we can solve in this manner, and actually say a lot about the possible solutions

Definition A linear homogeneous recurrence relation of degree kk with constant coefficients is one of the form

(5) an=c1an−1+c2an−2+⋯+ckan−k,n⩾ka_{n}=c_{1} a_{n-1}+c_{2} a_{n-2}+\cdots+c_{k} a_{n-k},\quad n \geqslant k
where c1,c2,⋯ ,ckc_{1}, c_{2}, \cdots, c_{k} are constants and ck≠0c_{k} \neq 0,

linear: the R.H.S. of 5 is a linear combination of an−1,⋯ ,an−ka_{n-1}, \cdots, a_{n-k}

homogeneous: no terms that are not multiples of an−1,⋯ ,an−ka_{n-1}, \cdots, a_{n-k} so no n powers

constant coefficients: coefficients of an−1,⋯ ,qn−ka_{n-1}, \cdots, q_{n-k} don't depend on nn

degree k: ana_{n} depends on the previous kk terms an−1,⋯ ,an−ka_{n-1}, \cdots, a_{n-k}

Of our examples so far

  1. linear homogeneous, degree 1, const coefficients
  2. linear homogeneous, degree 2, const coefficients
  3. linear homogeneous, degree 2, const coefficients
  4. linear non-homogeneous, degree 1, const coefficients

An example of a non-linear recurrence relation would be

an=an−1+an−22, a_{n}=a_{n-1}+a_{n-2}^{2},

and an=nan−1+4an−2a_{n}=n a_{n-1}+4 a_{n-2} is homogenous
linear without constant coefficients

The study of linear recurrence relations relies heavily on the techniques of linear algebra

As this is a brief intro, we wont explore the theory in great detail but instead consider some basic results

The key to our development of closed solutions lies in our reconsideration of example (1)

There we found an=a0⋅2na_{n}=a_{0} \cdot 2^{n} and so let us look for solutions of 5 of the form

an=a⋅rn a_{n}=a \cdot r^{n}

If we substitute this in 5 we get

arn=c1arn−1+c2arn−2+⋯+cka⋅rn−k a r^{n}=c_{1} a r^{n-1}+c_{2} a r^{n-2}+\cdots+c_{k} a \cdot r^{n-k}

Now divide by arn−k{ar}^{n-k} and rearrange to get

p(r)=rk−c1rk−1−c2rk−2−⋯−ck−1r−ck=0 p(r)=r^{k}-c_{1} r^{k-1}-c_{2} r^{k-2}-\cdots-c_{k-1} r-c_{k}=0

Note p(r)=rk−c1rk−1−⋯−ckp(r)=r^{k}-c_{1} r^{k-1}-\cdots-c_{k} is called the characteristic polynomial of the linear, homogenous, recurrence relation with constant coefficients
an=c1an−1+⋯+ckan−k,ck≠0a_{n}=c_{1} a_{n-1}+\cdots+c_{k} a_{n-k}, c_{k} \neq 0 and an=a⋅rna_{n}=a \cdot r^{n} is a solution of 5 iff P(r)=0P(r)=0

Facts

  1. The zeros of p(r)p(r) determine all the solutions of 5
  2. A recurrence relation of degree kk has kk-degrees of freedom
    This means that there will be kk arbitrary constants in a general solution of 5
  3. For every initial condition we impose on a solution, we eliminate a degree of freedom/
    ∴\therefore 1 initial conditions ⇒\Rightarrow unique solution

(as we have seen in our examples)

(4)

The Principle of Superposition

Any linear combination of solutions of 5 is again a solution of 5

That is, if {an1},{an2},⋯ ,{an2}\left\{a_{n}^{1}\right\},\left\{a_{n}^{2}\right\}, \cdots,\left\{a_{n}^{2}\right\} are solutions of 5 then so is

{a1an1+a2an2+⋯+a1anl}\left\{a_{1} a_{n}^{1}+a_{2} a_{n}^{2}+\cdots+a_{1} a_{n}^{l}\right\},
This is because 5 is a linear homogeneous recurrence relation


We now turn our attention to 2nd order homogenous linear recurrence relations with constant coefficients because they are completely solvable, (Proofs omitted)

Let us suppose, c1,c2∈Rc_{1}, c_{2} \in \mathbb{R} are given constants,

an=c1an−1+c2an−2 a_{n}=c_{1} a_{n-1}+c_{2} a_{n-2}

The characteristic polynomial equation for above is

See p(r)=r2−c1r−c2=0 p(r)=r^{2}-c_{1} r-c_{2}=0

The equation p(r)=0p(r)=0 has either

  1. 22 real distinct solutions r1,r2r_{1}, r_{2}
  2. 11 real solution, r1r_{1} "zero of order 2 "!
  3. 22 complex conjugate solutions,
    r1=a+ibr2=a−ibi2=−1r_{1}=a+i b\\ r_{2}=a-i b\\ i^{2}=-1

Case 1 p(r)=0p(r)=0 has 2 real roots r1,r2r_{1}, r_{2}

Then every solution of 7 is of the form an=a1r1n+a2r2na_{n}=a_{1} r_{1}^{n}+a_{2} r_{2}^{n} where a1,a2a_{1}, a_{2} are arbitrary real numbers. If we set 1 initial condition we will be able to write a2a_{2} in terms of a1a_{1}. If we set 2 initial conditions we will determine a1,a2a_{1}, a_{2} uniquely

Example Let an=an−1+2an−2,n⩾2a_{n}=a_{n-1}+2 a_{n-2},\qquad n \geqslant 2 (9)

The characteristic equation for (9) is r2−r−2=(r+1)(r−1)=0r^2 - r -2=(r+1)(r-1)=0
Thus r1=−1,r2=2r_{1}=-1, r_{2}=2 and every solution of (9) has the form

an=a1(−1)n+a22n,n⩾0(10) a_{n}=a_{1}(-1)^{n}+a_{2} 2^{n},\qquad n \geqslant 0 \quad\text{(10)}

If we now impose the condition a0=1a_{0}=1, we substitute n=0n=0 in (10) to get

1=a1+a2 or a2=1−a1 1=a_{1}+a_{2} \textit{ or } a_{2}=1-a_{1}

and then

an=a1(−1)n+(1−a1)2n(11) a_{n}=a_{1}(-1)^{n}+\left(1-a_{1}\right) 2^{n} \quad\text{(11)}

If we now insist that a1=−2a_{1}=-2, we substitute n=1n=1 in (11) to get

−2=a1(−1)1+(1−a1)21=2−3a1 -2=a_{1}(-1)^{1}+\left(1-a_{1}\right) 2^{1}=2-3 a_{1}

and 3a1=4⇒a1=43⋅(1−43=−13)3 a_{1}=4 \Rightarrow a_{1}=\frac{4}{3} \cdot \left(1-\frac{4}{3}=-\frac{1}{3}\right)

Thus an=43(−1)n−132na_{n}=\frac{4}{3}(-1)^{n}-\frac{1}{3} 2^{n} is the unique solution of the Initial Value recurrence relation (13)

an=an−1+2an−2,n=2,3,⋯a0= 1a1=−2 \begin{array}{l} a_{n}=a_{n-1}+2 a_{n-2},\quad n=2,3, \cdots \\ a_{0}=\ 1 \\ a_{1}=-2 \end{array}

Case 2p(r)=0\quad p(r)=0 has one real root r1r_{1}

Then every solution of 7 is of the form

an=(a1+a2n)r1n, where  a_{n}=\left(a_{1}+a_{2} n\right) r_{1}^{n} \text {, where }

a1,a2a_{1}, a_{2} are arbitrary real numbers. The same comments on initial conditions still hold. (For case 3 as well)

Example Consider the recurrence relation

an=an−1+an−2p(r)=r2−r−1=0∴r=1±(−1)2−4(1)(−1)2=1±52∴an=a1(1+52)n+a2(1−52)n \begin{aligned} & a_{n}=a_{n-1}+a_{n-2} \\ & p(r)=r^{2}-r-1=0 \\ & \therefore \quad r=\frac{1 \pm \sqrt{(-1)^{2}-4(1)(-1)}}{2}=\frac{1 \pm \sqrt{5}}{2} \\[2em] & \therefore \quad a_{n}=a_{1}\left(\frac{1+\sqrt{5}}{2}\right)^{n}+a_{2}\left(\frac{1-\sqrt{5}}{2}\right)^{n} \end{aligned}

Let φ=1+52,−1φ=1−52\varphi=\frac{1+\sqrt{5}}{2},-\frac{1}{\varphi}=\frac{1-\sqrt{5}}{2} and an=a1φn+a2(−1φ)na_{n}=a_{1} \varphi^{n}+a_{2}\left(\frac{-1}{\varphi}\right)^{n}

Exercises

  1. If a0=a1=1a_{0}=a_{1}=1, find a1,a2a_{1}, a_{2}.
  2. What is φ=1+52\varphi=\frac{1+\sqrt{5}}{2} called?

Example Let an=an−1−14an−2a_{n}=a_{n-1}-\frac{1}{4} a_{n-2}

The characteristic equation is r2−r+14=0r^{2}-r+\frac{1}{4}=0 That is,

(r−12)2=0\left(r-\frac{1}{2}\right)^{2}=0, so r1=12r_{1}=\frac{1}{2} is the sole real solution.

Thus every solution of equation is of the from

an=(a1+a2n)(12)n a_{n}=\left(a_{1}+a_{2} n\right)\left(\frac{1}{2}\right)^{n}

If we now require a0=2,a1=6a_{0}=2, a_{1}=6, we have, by above,

n=0:2=a1:n=1:6=(a1+a2)12 \begin{aligned} & n=0: 2=a_{1}: \\ & n=1: \quad 6=\left(a_{1}+a_{2}\right) \frac{1}{2} \end{aligned}

Thus 12=2+a2,a2=1012=2+a_{2}, a_{2}=10.

Thus the solution to

an=an−1−14an−2,n⩾2a0=2a1=6 \begin{aligned} & a_{n}=a_{n-1}-\frac{1}{4} a_{n-2},\quad n \geqslant 2 \\ & a_{0}=2 \\ & a_{1}=6 \end{aligned} is an=(2+10n)(12)n=(1+5n)2n−1 \textrm{is }\qquad a_{n}=(2+10 n)\left(\frac{1}{2}\right)^{n}=\frac{(1+5 n)}{2^{n-1}}

Example What is a10a_{10} ?

Case 3 p(r)p(r) has 2 complex conjugates roots:

r1=a+ibr2=a−ib r_1=a+ib\\ r_{2}=a-i b

Then every solution of 7 is of the form

an=Rn(a1cos⁡nθ+a2sin⁡nθ) a_{n}=R^{n}\left(a_{1} \cos n \theta+a_{2} \sin n \theta\right)

where R=a2+b2R=\sqrt{a^{2}+b^{2}}, and θ\theta is the unique angle, 0≤θ<2π0 \leq \theta<2 \pi such that

cos⁡θ=aR,sin⁡θ=bR. \cos \theta=\frac{a}{R}, \sin \theta=\frac{b}{R} .

Note This case is not covered in the text
(§\S 8.18.1 and 8.28.2 on recurrence relations - read these sections and examples for the other cases)

Limits of Ratios of solutions to recurrence relations have importance in other topics in math

Suppose {an}\left\{a_{n}\right\} is a solution of the recurrence relation

(7) an=c1an−1+c2an−2,n⩾2a_{n}=c_{1} a_{n-1}+c_{2} a_{n-2},\quad n \geqslant 2

Suppose lim⁡n→+∞(anan−1)=L≠0\displaystyle\lim _{n \rightarrow+\infty}\left(\frac{a_{n}}{a_{n-1}}\right)=L\neq 0 is a finite number.

Then if we divide (7) by an−1a_{n-1} we get

anan−1=c1+c2an−2an−1=c1+c2[an−1an−2] \begin{aligned} \frac{a_{n}}{a_{n-1}} & =c_{1}+c_{2} \frac{a_{n-2}}{a_{n-1}} \\ & =c_{1}+\frac{c_{2}}{\left[\frac{a_{n-1}}{a_{n-2}}\right]} \end{aligned}

Now let n→+∞n \rightarrow+\infty to get

L=c1+C2L,orL2=c1L+c2 \begin{aligned} & L=c_{1}+\frac{C_{2}}{L}, or \\ & L^{2}=c_{1} L+c_{2} \end{aligned}

ie, L2−c1L−c2=0L^{2}-c_{1} L-c_{2}=0 Thus p(L)=0p(L)=0, where p(r)p(r) is the
characteristic polynomial for (7)

Thus lim⁡n→∞anan−1=r11\displaystyle\lim _{n \rightarrow \infty} \frac{a_{n}}{a_{n-1}}=r_{11} or r2r_{2}.

Which one will depend on the initial conditions. (18)

Example Solve an=2an−1+8an−2a_{n}=2 a_{n-1}+8 a_{n-2}

a0=5,a1=2 a_{0}=5, \quad a_{1}=2

Solution The characteristic equation is

r2−2r−8=0(r+2)(r−4)=0∴ r=−2,4 \begin{aligned} r^{2}-2 r-8&=0 \\ (r+2)(r-4)&=0 \\ \therefore \ r&=-2,4 \end{aligned}

Thus an=a1(−2)n+a24na_{n}=a_{1}(-2)^{n}+a_{2} 4^{n}

n=0‾a0=5=x1+x2a1=2=−2a1+4a2 \begin{array}{ll} \underline{n=0} & a_{0}=5=x_{1}+x_{2} \\ &a_{1}=2=-2 a_{1}+4 a_{2} \end{array}

In matrix form [11−24][a1a2]=[52]\left[\begin{array}{cc}1 & 1 \\ -2 & 4\end{array}\right]\left[\begin{array}{l}a_{1} \\ a_{2}\end{array}\right]=\left[\begin{array}{l}5 \\ 2\end{array}\right]

∴[a1x2]=[11−.24]−1[52]=16[4−121][52]=16[1812]=[32]∴an=3(−2)n+2⋅4n ie an=3(−2)n+22n+1 \begin{aligned} \therefore\left[\begin{array}{l} a_{1} \\ x_{2} \end{array}\right] & =\left[\begin{array}{cc} 1 & 1 \\ -.2 & 4 \end{array}\right]^{-1}\left[\begin{array}{l} 5 \\ 2 \end{array}\right]=\frac{1}{6}\left[\begin{array}{cc} 4 & -1 \\ 2 & 1 \end{array}\right]\left[\begin{array}{l} 5 \\ 2 \end{array}\right] \\ & =\frac{1}{6}\left[\begin{array}{c} 18 \\ 12 \end{array}\right]=\left[\begin{array}{l} 3 \\ 2 \end{array}\right] \\ \therefore \quad a_{n} & =3(-2)^{n}+2 \cdot 4^{n} \\ \text { ie } a_{n} & =3(-2)^{n}+2^{2 n+1} \end{aligned}

Example Solve an=52an−1−an−2a_{n}=\frac{5}{2} a_{n-1}-a_{n-2} for a0=1,a1=0 a_{0}=1, a_{1}=0

Solution Characteristic, equation

r2−52r−1=0ie2r2−5r−2=0 \begin{aligned} & r^{2}-\frac{5}{2} r-1=0 \\ ie\qquad& 2 r^{2}-5 r-2=0 \end{aligned} a=2,b=−5,c=−2r=5±25+164=5±414∴an=a1(5+414)n+a2(5−414)na0=1=a1+a2a1=0=a1(5+414)+a2(5−414) \begin{gathered} a=2, \quad b=-5, \quad c=-2 \\[1em] r=\frac{5 \pm \sqrt{25+16}}{4}=\frac{5 \pm \sqrt{41}}{4} \\[1em] \therefore \quad a_{n}=a_{1}\left(\frac{5+\sqrt{41}}{4}\right)^{n}+a_{2}\left(\frac{5-\sqrt{41}}{4}\right)^{n} \\ a_{0}=1=a_{1}+a_{2} \\ a_{1}=0=a_{1}\left(\frac{5+\sqrt{41}}{4}\right)+a_{2}\left(\frac{5-\sqrt{41}}{4}\right) \end{gathered}

Exercise Find a1,a2a_{1}, a_{2}.

 P551#3,4  \text { P551\#3,4 }